/**
 *
 * @author Alex & Umit
 */


import java.util.*;

public class BinTree
{
    private TNode root;
    private int size;

    public BinTree()
    {
        root = null;
        size = 0;
    }
	    
    public boolean isEmpty()
    {
                return root == null;
    }
		
    public int size()
    {
            return size;
    }
		
    public void addRoot(Object o)
    {
        if(isEmpty())
        {
           root = new TNode(o,null,null,null);
           size++;
        }
        else throw new NonEmptyTreeException("attempting to add to !empty tree");
    }
		
    public Position root()
    {
        if (!isEmpty())
            return root;
        else
            throw new EmptyTreeException("attempting to return empty tree");
    }
		
    public boolean isRoot(Position p)
    {
        TNode t = (TNode)p;
        return p == root;
    }

		public boolean hasLeft(Position p)
		{
           TNode t = (TNode)p;
           return t.left() != null;
  		}

  		public boolean hasRight(Position p)
		{
           TNode t = (TNode)p;
           return t.right() != null;
  		}
  		
  		public void insertLeft(Position p, Object o)
  		{
			if(!hasLeft(p))
			{
				TNode t = (TNode)p;
				t.setLeft(new TNode(o, t, null, null));
				size++;
			}
			else
          	 	throw new InvalidPositionException("Already have a left child!");
		}

		public void insertRight(Position p, Object o)
  		{
			if(!hasRight(p))
			{
				TNode t = (TNode)p;
				t.setRight(new TNode(o, t, null, null));
				size++;
			}
			else
            	throw new InvalidPositionException("Already have a right child!");
		}
		
		public Position leftChild(Position p)
		{
			if(hasLeft(p))
			{
				TNode t =(TNode)p;
				return t.left();
			}
			else
				throw new BoundaryViolationException("no left child");
		}
		
		public Position rightChild(Position p)
		{
			if(hasRight(p))
			{
				TNode t =(TNode)p;
				return t.right();
			}
			else
				throw new BoundaryViolationException("no right child");
		}
		
		public boolean isLeft(Position p)
		{
			TNode t = (TNode)p;
			return t == t.parent().left();
		}
		
		public boolean isRight(Position p)
		{
			TNode t = (TNode)p;
			return t == t.parent().right();
		}
		
		public boolean hasParent(Position p)
		{
			TNode t = (TNode)p;
			return (t.parent() != null);
		}
		
		public Position parent(Position p)
		{
			if(hasParent(p))
			{
				TNode t = (TNode)p;
				return t.parent();
			}
			else
            	throw new BoundaryViolationException("no parent");	
  		}

		public boolean isInternal(Position p)
		{
			if(hasLeft(p) || hasRight(p))
			{
				return true;
			}
			else
				return false;
		}
		
		public boolean isExternal(Position p)
		{
			return !isInternal(p);
		}
		
		public Object replaceElement(Position p, Object e)
		{
			Object tmp = (Object)toTNode(p).element();
        	toTNode(p).setElem(e);
        	return tmp;
    	}
    	
    	 public void swapElement(Position p, Position q)
    	{
	        TNode first = toTNode(p);
	        TNode second = toTNode(q);
	        Object tmp = first.element();
	
	        first.setElem(second.element());
	        second.setElem(tmp);
    	}

        public int depth(Position p)
    	{
	        // return 0 if p is the root node else recursively calculate depth
	        return isRoot(p) ? 0 : 1 + depth(parent(p));
    	}

        public int size(Position p)
    	{
        
	         if(hasLeft(p) && hasRight(p))
	            return 1 + size(leftChild(p)) + size(rightChild(p));
	
	        else if(hasRight(p) && !hasLeft(p))
	            return 1 + size(rightChild(p));
	
	        else if(!hasRight(p) && hasLeft(p))
	            return 1 + size(leftChild(p));
	         
	        else return 1;
    	}
    	
    	 public Iterator positions()
    	{
	        ArrayList<Object> tmp = new ArrayList<Object>(size());
	        
	        inorderPositions(root(), tmp);
	        
	        return tmp.iterator();
    	}
    	
    	public Iterator elements()
    	{
	        ArrayList<Object> tmp = new ArrayList<Object>(size());
	
	        inorderElements(root(), tmp);
	
	        return tmp.iterator();
    	}


        private void inorderPositions(Position p, ArrayList<Object> aList)
    	{
	        if (hasLeft(p))
	            inorderPositions(leftChild(p), aList);
	
	        aList.add(aList.size(), toTNode(p));
	
	        if (hasRight(p))
	            inorderPositions(rightChild(p), aList);
    	}
    	
    	private void inorderElements(Position p, ArrayList<Object> aList)
    	{
	        if (hasLeft(p))
	            inorderElements(leftChild(p), aList);
	
	        aList.add(aList.size(), toTNode(p).element());
	
	        if (hasRight(p))
	            inorderElements(rightChild(p), aList);
    	}


		public String toString()
		{
			if(isEmpty())
				throw new EmptyTreeException("toString()");
			else 
				return toString(root,0);
		}
		
		public String toString(Position p, int indents)
		{
			String tab = "    ";
			String tabs = "";
			for(int i = 0; i < indents; i++)
				tabs = tabs + tab;
			
			TNode t = (TNode)p;
			String res = "";
			res = tabs + "<BinTree(" + t;
			if (t.left() != null)
				res = res + "\n" + toString(t.left(),indents + 1);
			else 
				res = res + "\n" + tabs + tab + "()";
			if(t.right() != null)
				res = res + "\n" + toString(t.right(),indents + 1);
			else 
				res = res + "\n" + tabs + tab + "()";
			res = res + "\n" + tabs + ")>";
			return res;
		}
		
		protected TNode toTNode(Position p)
		{

        // helper cast function
        	if(p == null) throw new NullPointerException();
        	if (p instanceof TNode)
            	return (TNode) p;
        	else
            	throw new AssertionError("casting error");
  		}

}